Binary Search একটি দ্রুত সার্চিং পদ্ধতি যা শুধুমাত্র সন্নিবেশিত (sorted) তালিকার উপর কাজ করে। এটি তালিকাকে পুনরায় বিভক্ত করে লক্ষ্য উপাদানটি খুঁজে বের করে, এবং এর সময় জটিলতা O(log n)।
Binary Search এর কাজের পদ্ধতি:
- তালিকার মধ্যবর্তী উপাদান নির্ধারণ করুন।
- লক্ষ্য উপাদানটি মধ্যবর্তী উপাদানের থেকে ছোট হলে বাম দিকের অংশে অনুসন্ধান করুন, আর বড় হলে ডান দিকের অংশে অনুসন্ধান করুন।
- এই প্রক্রিয়াটি তখন পর্যন্ত চলতে থাকে যতক্ষণ না লক্ষ্য উপাদান পাওয়া যায় বা তালিকার অংশটি খালি হয়ে যায়।
Binary Search এর গঠন
#include <stdio.h>
// Function to perform binary search
int binarySearch(int arr[], int size, int target) {
int left = 0;
int right = size - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // Find the middle index
// Check if the target is present at mid
if (arr[mid] == target) {
return mid; // Return index if target is found
}
// If target is greater, ignore left half
if (arr[mid] < target) {
left = mid + 1;
}
// If target is smaller, ignore right half
else {
right = mid - 1;
}
}
return -1; // Return -1 if target is not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50}; // Sorted array
int size = sizeof(arr) / sizeof(arr[0]);
int target = 30; // Element to search for
int result = binarySearch(arr, size, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
১. কোড বিশ্লেষণ
binarySearch ফাংশন:
- ইনপুট হিসেবে একটি সন্নিবেশিত অ্যারে, এর সাইজ এবং লক্ষ্য উপাদান গ্রহণ করে।
- দুইটি সূচক
leftএবংrightদিয়ে শুরু হয়। - একটি লুপের মাধ্যমে মধ্যবর্তী উপাদান খুঁজে বের করে এবং লক্ষ্য উপাদানের সাথে তুলনা করে।
- যদি লক্ষ্য উপাদান পাওয়া যায়, তবে ইনডেক্স ফেরত দেয়।
- যদি লক্ষ্য উপাদান মধ্যবর্তী উপাদানের থেকে ছোট হয়, তবে
leftআপডেট করা হয়। অন্যথায়,rightআপডেট করা হয়। - যদি লক্ষ্য উপাদান না পাওয়া যায়, তাহলে -1 ফেরত দেয়।
main ফাংশন:
- একটি সন্নিবেশিত উদাহরণ অ্যারে তৈরি করে এবং একটি লক্ষ্য উপাদান নির্ধারণ করে।
binarySearchফাংশন কল করে এবং ফলাফল প্রিন্ট করে।
২. Binary Search এর সময় জটিলতা
- Worst Case: O(log n) - যখন সবচেয়ে কম সংখ্যক পরিদর্শন করা হয়।
- Best Case: O(1) - যদি লক্ষ্য উপাদান মধ্যবর্তী উপাদান হয়।
- Average Case: O(log n) - গড় ক্ষেত্রে।
Content added By
Read more
